package com.moyoutian.leetcode.jianzhi;

/**
 * 给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%'。
 * <p>
 * 注意：
 * 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8以及truncate(-2.7335) = -2
 * 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231,231−1]。本题中，如果除法结果溢出，则返回 231− 1
 * <p>
 * 示例 1：
 * <p>
 * 输入：a = 15, b = 2
 * 输出：7
 * 解释：15/2 = truncate(7.5) = 7
 * 示例 2：
 * <p>
 * 输入：a = 7, b = -3
 * 输出：-2
 * 解释：7/-3 = truncate(-2.33333..) = -2
 * 示例 3：
 * <p>
 * 输入：a = 0, b = 1
 * 输出：0
 * 示例 4：
 * <p>
 * 输入：a = 1, b = 1
 * 输出：1
 * <p>
 * <p>
 * 提示:
 * <p>
 * -231<= a, b <= 231- 1
 * b != 0
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/xoh6Oh
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Demo1 {

    public static void main(String[] args) {
        System.out.println(divide(-2147483648, 2));
    }

    /**
     * 这部中符号是必须的，特殊处理部分是判断优化
     */
    public static int divide(int a, int b) {
        //特殊处理
        if (a == 0) {
            return 0;
        }
        if (a == b) {
            return 1;
        }
        if (b == 1) {
            return a;
        }
        if (b == -1) {
            return Integer.MIN_VALUE == a ? Integer.MAX_VALUE : -a;
        }
        //符号处理
        if ((long) a > 0 && (long) b > 0) {
            return (int) positiveNumber(a, b);
        } else if (a < 0 && b < 0) {
            return (int) positiveNumber(-(long) a, -(long) b);
        } else if (a < 0) {
            return -(int) positiveNumber(-(long) a, b);
        } else if (b < 0) {
            return -(int) positiveNumber(a, -(long) b);
        } else {
            return (int) positiveNumber(a, b);
        }
    }

    /**
     * 都是正数的计算
     */
    public static long positiveNumber(long a, long b) {
        if (a < b) {
            return 0;
        }
        //除数
        long temp = b;
        long count = 1;
        // 拆解成减法 10/3 -> 10-3*2-3*1  -> 10-(3<<1)-(3<<0)
        // 位运算超过int最大值会变负数，根据除数算出当前最大的可减数  比如 40/9 -> 40-9*2*2 ,其中的 9*2*2 用位运算算出。
        // 如果当前的还未算进就用 减出的结果接着往下算
        while ((temp << 1) < a && (temp << 1) > 0) {
            temp = temp << 1;
            count *= 2;
        }
        return (count + positiveNumber((a - temp), b));
    }
}
